//算法:顺序查找、折半查找和分块查找
#include<stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXSIZE 300000000
#define b 150000
#define s 2000
#define OK 1;

typedef struct{
	int key;//关键字域
}ElemType;

typedef struct{
	int key;
	int addr_start;
}BlockIndex;

typedef struct{
	ElemType *R;
	BlockIndex *index;
	int length;
}SSTable;

int InitList_SSTable(SSTable *L)
{
	L->R=(ElemType *)malloc(sizeof(ElemType)*MAXSIZE);
	L->index=(BlockIndex *)malloc(sizeof(BlockIndex)*b);
	if (!L->R)
	{
		printf("初始化错误");
		return 0;
	}
	else{
		printf("初始化成功size=%d\n",MAXSIZE);
	}
	L->length=0;
	return OK;
}

int Insert_SSTable(SSTable *L) 
{
	int j=0;
	int bi=1;
	for(int i=0;i<MAXSIZE+1;i++)
	{
		L->R[i].key=j;
		int k=i%s;
		//printf("k=%d;S=%d\n",k,S);
		if(k==1){
			L->index[bi].key=j;
			L->index[bi].addr_start=i;
			bi++;
		}
		L->length++;
		j++;
	}
	return 1;
}

int Search_Seq(SSTable *ST, int key){
    //在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为
    //该元素在表中的位置，否则为0
     for (int i=ST->length; i>=1; --i)  
             if (ST->R[i].key==key) return i;		//从后往前找        
     return 0;
}// Search_Seq

int Search_Bin(SSTable *ST,int key,int start,int end) {
   // 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为
   // 该元素在表中的位置，否则为0
   int low=start,high=end;							//置查找区间初值
   int  mid;
   while(low<=high) {
	   mid=(low+high) / 2;
      if (key==ST->R[mid].key)  return mid;      		//找到待查元素
      else if (key<ST->R[mid].key)  high = mid -1;		//继续在前一子表进行查找
      else  low =mid +1;                       			//继续在后一子表进行查找
   }//while
   return 0;										//表中不存在待查元素
}// Search_Bin

int Search_Block(SSTable *ST,int key) {
   // 分块查找
   int low=1,high=s;
   while(low<=high) {
	  //printf("ST->index[low].key=%d&&ST->index[low+1].key=%d\n",ST->index[low].key,ST->index[low+1].key);
      if (key>=ST->index[low].key&&key<ST->index[low+1].key){
			int i=Search_Bin(ST,key,ST->index[low].addr_start,ST->index[low+1].addr_start);
			if(i!=0){
				printf("找到%d的位置为%d,block=%d\n",key,i,low);
				return i;
			}
			low=low+1;
	  }
      else  low =low +1;
   }//while
   return 0;
}

void Show_End(int result,int testkey)
{
	if(result==0)
		printf("未找到%d\n",testkey);
	else
		printf("找到%d的位置为%d\n",testkey,result);
	return;
}
int main()
{
	SSTable *ST;
	ST=(SSTable *)malloc(sizeof(SSTable));
	InitList_SSTable(ST);
	Insert_SSTable(ST);
	int testkey1=MAXSIZE*0.001,testkey2=MAXSIZE*0.5;
	int result;
	clock_t start, end;
    double cpu_time_used;

    // Measure time for search operations
    start = clock();
	result=Search_Seq(ST, testkey1);
    end = clock();
	cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Time taken by Search_Seq: %f seconds\n", cpu_time_used);
	Show_End(result,testkey1);

	start = clock();
	result=Search_Bin(ST, testkey1,1,ST->length);
    end = clock();
	cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Time taken by Search_Bin: %f seconds\n", cpu_time_used);
	Show_End(result,testkey1);
	
	start = clock();
	result=Search_Seq(ST, testkey2);
    end = clock();
	cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Time taken by Search_Seq: %f seconds\n", cpu_time_used);

	start = clock();
	result=Search_Bin(ST, testkey2,1,ST->length);
    end = clock();
	cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Time taken by Search_Bin: %f seconds\n", cpu_time_used);
	Show_End(result,testkey2);

	start = clock();
	result=Search_Block(ST, testkey1);
    end = clock();
	cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Time taken by Search_Block: %f seconds\n", cpu_time_used);
	Show_End(result,testkey1);

	return 0;
}